import java.util.List;
import java.util.Stack;

/**
 * 
 */

/**
 * @author zhongfang
 *
 */
public class ReverseLinkedList {
	public class ListNode {
		 int val;
		 ListNode next;
		 ListNode(int x) { val = x; }
	}
	public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode last=head;
        ListNode cur=head.next;
        last.next=null;
        ListNode newHead=cur;
        while(cur!=null){
            ListNode tmp=cur.next;
            if(tmp!=null){
            	newHead=tmp;
            }
            cur.next=last;
            cur=tmp;
        }
        return newHead;
    }
//	public ListNode reverseList(ListNode head) {
//        if(head==null)
//            return null;
//        Stack<ListNode> stack=new Stack<>();
//        while(head!=null){
//            stack.add(head);
//            head=head.next;
//        }
//        ListNode cur=stack.pop();
//        ListNode newHead=cur;
//        while(!stack.isEmpty()){
//            ListNode newNode=stack.pop(); 
//            newNode.next=null;
//            cur.next=newNode;
//            cur=newNode;
//        }
//        return newHead;
//    }
	
//	public ListNode reverseList(ListNode head) {
//		if(head==null)
//			return null;
//        if(head.next==null){
//        	return head;
//        }
//        ListNode allHead=reverseList(head.next);
//        head.next.next=head;
//        head.next=null;
//        return allHead;
//    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ReverseLinkedList reverseLinkedList=new ReverseLinkedList();
		ListNode nd1=reverseLinkedList.new ListNode(1);
		ListNode nd2=reverseLinkedList.new ListNode(2);
		nd1.next=nd2;
		
		ListNode cur=reverseLinkedList.reverseList(nd1);
		while (cur!=null) {
			System.out.println(cur.val);
			cur=cur.next;
		}
	}

}
